#pragma once

#include<iostream>
using namespace std;

class Solution
{
public:
    // int tribonacci(int n) 
    // {
    //     if(n == 0)  return 0;
    //     if(n == 1|| n == 2)  return 1;

    //     return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3);
    // }

    int tribonacci(int n)
    {
        if (n == 0)
        {
            return 0;
        }
        if (n == 1 || n == 2)
        {
            return 1;
        }

        int* a = new int[n + 1];

        a[0] = 0;
        a[1] = 1;
        a[2] = 1;

        for (int i = 3; i < n + 1; ++i)
        {
            a[i] = a[i - 1] + a[i - 2] + a[i - 3];
        }

        int tmp = a[n];
        delete[] a;
        a = nullptr;

        return tmp;
    }

    // int tribonacci(int n) 
    // {
    //     int a = 0,b = 1,c = 1,d = 0;
    //     if(n == 0)  return 0;
    //     if(n == 1|| n == 2)  return 1;

    //     for(int i = 3;i <= n;++i)
    //     {
    //         d = a + b + c;
    //         a = b; 
    //         b = c;
    //         c = d;
    //     }

    //     return d;
    // }
};